home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / lysrc.zip / YACCCLOS.PAS < prev    next >
Pascal/Delphi Source File  |  1993-01-24  |  5KB  |  140 lines
  1.  
  2. unit YaccClosure;
  3.  
  4. (* 2-16-91 AG *)
  5.  
  6. (* Copyright (c) 1990,91 by Albert Graef, Schillerstr. 18,
  7.    6509 Schornsheim/Germany
  8.    All rights reserved *)
  9.  
  10. interface
  11.  
  12. (* Yacc closure and first set construction algorithms. See Aho/Sethi/Ullman,
  13.    1986, Sections 4.4 and 4.7, for further explanation. *)
  14.  
  15. procedure closures;
  16.   (* compute the closure sets *)
  17.  
  18. procedure first_sets;
  19.   (* compute first sets and nullable flags *)
  20.  
  21. implementation
  22.  
  23. uses YaccBase, YaccTables;
  24.  
  25. procedure closures;
  26.  
  27.   (* The closure set of a nonterminal X is the set of all nonterminals Y
  28.      s.t. Y appears as the first symbol in a rightmost derivation from the
  29.      nonterminal X (i.e. X =>+ Y ... in a rightmost derivation). We can
  30.      easily compute closure sets as follows:
  31.      - Initialize the closure set for any nonterminal X to contain all
  32.        nonterminals Y for which there is a rule X : Y ...
  33.      - Now repeatedly pass over the already constructed sets, and for
  34.        any nonterminal Y which has already been added to the closure set
  35.        of some nonterminal X, also include the closure elements of Y in
  36.        the closure set of X.
  37.      The algorithm terminates as soon as no additional symbols have been
  38.      added during the previous pass. *)
  39.  
  40.   var sym, i, count, prev_count : Integer;
  41.       act_syms : IntSet;
  42.  
  43.   begin
  44.     (* initialize closure sets: *)
  45.     prev_count := 0;
  46.     count := 0;
  47.     for sym := 1 to n_nts do
  48.       begin
  49.         closure_table^[sym] := newEmptyIntSet;
  50.         with rule_offs^[sym] do
  51.           for i := rule_lo to rule_hi do
  52.             with rule_table^[rule_no^[i]]^ do
  53.               if (rhs_len>0) and (rhs_sym[1]<0) then
  54.                 include(closure_table^[sym]^, rhs_sym[1]);
  55.         inc(count, size(closure_table^[sym]^));
  56.       end;
  57.     (* repeated passes until no more symbols have been added during the last
  58.        pass: *)
  59.     while prev_count<count do
  60.       begin
  61.         prev_count := count;
  62.         count := 0;
  63.         for sym := 1 to n_nts do
  64.           begin
  65.             act_syms := closure_table^[sym]^;
  66.             for i := 1 to size(act_syms) do
  67.               setunion(closure_table^[sym]^, closure_table^[-act_syms[i]]^);
  68.             inc(count, size(closure_table^[sym]^));
  69.           end;
  70.       end;
  71.   end(*closures*);
  72.  
  73. procedure first_sets;
  74.  
  75.   (* The first set of a nonterminal X is the set of all literal symbols
  76.      y s.t. X =>+ y ... in some derivation of the nonterminal X. In
  77.      addition, X is nullable if the empty string can be derived from X.
  78.      Using the first set construction algorithm of Aho/Sethi/Ullman,
  79.      Section 4.4, the first sets and nullable flags are computed as
  80.      follows:
  81.  
  82.      For any production X -> y1 ... yn, where the yi are grammar symbols,
  83.      add the symbols in the first set of y1 (y1 itself if it is a literal)
  84.      to the first set of X; if y1 is a nullable nonterminal, then proceed
  85.      with y2, etc., until either all yi have been considered or yi is non-
  86.      nullable (or a literal symbol). If all of the yi are nullable (in
  87.      particular, if n=0), then also set nullable[X] to true.
  88.  
  89.      This procedure is repeated until no more symbols have been added to any
  90.      first set and none of the nullable flags have been changed during the
  91.      previous pass. *)
  92.  
  93.   var i, j, l, sym : Integer;
  94.       n, null, done : Boolean;
  95.  
  96.   begin
  97.     (* initialize tables: *)
  98.     for sym := 1 to n_nts do
  99.       begin
  100.         nullable^[sym] := false;
  101.         first_set_table^[sym] := newEmptyIntSet;
  102.       end;
  103.     (* repeated passes until no more symbols added and no nullable flags
  104.        modified: *)
  105.     repeat
  106.       done := true;
  107.       for i := 1 to n_rules do
  108.         with rule_table^[i]^ do
  109.           begin
  110.             l := size(first_set_table^[-lhs_sym]^);
  111.             n := nullable^[-lhs_sym];
  112.             null := true;
  113.             j := 1;
  114.             while (j<=rhs_len) and null do
  115.               begin
  116.                 if rhs_sym[j]<0 then
  117.                   begin
  118.                     setunion( first_set_table^[-lhs_sym]^,
  119.                               first_set_table^[-rhs_sym[j]]^ );
  120.                     null := nullable^[-rhs_sym[j]];
  121.                   end
  122.                 else
  123.                   begin
  124.                     include( first_set_table^[-lhs_sym]^,
  125.                              rhs_sym[j] );
  126.                     null := false;
  127.                   end;
  128.                 inc(j);
  129.               end;
  130.             if null then nullable^[-lhs_sym] := true;
  131.             if (l<size(first_set_table^[-lhs_sym]^)) or
  132.                (n<>nullable^[-lhs_sym]) then
  133.               done := false;
  134.           end;
  135.     until done;
  136.   end(*first_sets*);
  137.  
  138. end(*YaccClosure*).
  139.  
  140.